package com.lw.leetcode.dp.b;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 372. 超级次方
 *
 * @author liw
 * @version 1.0
 * @date 2021/9/22 14:43
 */
public class SuperPow {


    public static void main(String[] args) {
        SuperPow test = new SuperPow();

        // 1198
//        int a = 2147483647;
//        int[] b = {2,0,0};


        // 36
        int a = 24564212;
        int[] b = {3, 5, 8, 9, 6, 0, 2, 3, 0, 1, 5, 0, 2, 3, 0, 1, 0, 0, 2, 3, 6};

        int i = test.superPow(a, b);
        System.out.println(i);
    }

    public int superPow(int a, int[] b) {

        a %= 1337;
        if (a < 2) {
            return a;
        }
        int length = b.length;
        long[] arr = new long[length];
        arr[length - 1] = a;

        int[] ca = new int[1337];
        for (int i = length - 2; i >= 0; i--) {
            long v = arr[i + 1];
            int s = ca[(int) v];
            if (s == 0) {
                s = (int) ((v * v * v * v % 1337) * (v * v * v * v % 1337) * v * v % 1337);
                ca[(int) arr[i + 1]] = s;
            }
            arr[i] = s;
        }
        int sum = 1;
        System.out.println(Arrays.toString(ca));
        System.out.println(Arrays.toString(arr));
        for (int i = 0; i < length; i++) {
            int c = b[i];
            long v = arr[i];
            for (int j = 0; j < c; j++) {
                sum = (int) (sum * v % 1337);
            }
            System.out.println(i + "    " + sum);
        }
        return sum % 1337;
    }

}
